/*
 * @lc app=leetcode id=15 lang=cpp
 *
 * [15] 3Sum
 */
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> result;
        int len = nums.size();
        if (len < 3) {
            return result;
        }

        sort(nums.begin(), nums.end());

        for (int i=0; i<len; i++) {
            int target = -nums[i];
            int front = i+1;
            int tail = len-1;

            while (front < tail) {

                if (nums[front] + nums[tail] < target) {
                    front++;
                } else if (nums[front] + nums[tail] > target) {
                    tail--;
                } else {

                    vector<int> ret = {nums[front], nums[i], nums[tail]};
                    result.push_back(ret);

                    while (front < rear && nums[front] == nums[front+1]) {
                        font++;
                    }
                    while (front < rear && nums[tail-1] == nums[tail]) {
                        tail--;
                    }
                }
            }

            while (i+1<len && nums[i] == nums[i+1])
                i++;
        }
        return result;
    }
};

